Examples of networks over which one may wish to solve the problem of distributing information efficiently may be found in a variety of fields, including commerce, telecommunications, robotics, and military applications where a network of sensor nodes track targets. Various algorithms have been proposed for achieving solutions to this problem. The algorithms for solving this problem over a network fall into two classes:
Centralised Algorithms—for this class of algorithm, there is a requirement that all data be sent to a single node. The processing occurs at that node and the solution is sent out to all nodes. Because all decisions are taken in one place, the decisions (and the information upon which they are based) are consistent and can be easily coordinated. However, known centralised algorithms are not robust and do not scale well with network size. They are not robust since the removal of the central node causes complete failure. They do not scale well as the number of messages that must be sent down a given link will tend to grow with network size (or the number of links to the central node will grow).Distributed Algorithms—this applies to an architecture in which decisions concerning sensing, manoeuvring and communicating are made locally, even when in pursuit of some global goal.
Advantages: a distributed system has inherent robustness; potentially it has minimal time lag between decision and local action; and resource consumption patterns are more even, providing flexible deployment options.
Disadvantages: for known algorithms, the decisions made at different points may be inconsistent; co-ordination must be enabled across the network.
The inventors have recognised that the principal shortfalls of distributed decision making can be mitigated by designing better algorithms (to be described hereinafter) ensuring decisions are consistent, by providing consistent information to decision makers in an efficient way, by ensuring local and global goals are aligned and by developing better co-ordination strategies.
Computational Strategy In-Network or On-Network?
One way of thinking of a distributed system is to view it as a set of processors connected by a network that executes algorithms for fusion and decision making. The design decisions are then simple (in principle) and relate to provisioning the processing required by the algorithms and designing networks to cope with expected distribution of information sources and consumers.
An alternative is to adopt a more holistic view and consider computation to be a function of the distributed system itself. This provides the opportunity to develop algorithms that are more flexible and more efficient than simply replicating algorithms over a network. In the sensor network literature this is termed “In-Network” computation, for example see Reference [1]. By analogy, the former option is called “On-Network” computation.
It is instructive to consider now the scalability and resource efficiency of two hypothetical schemes for processing and communicating information in a network, one an In-Network solution, the other an On-network and construct a scaling-argument in favour of the In-Network case.
In this regard, it is instructive to consider two cases for a system composed of nodes (e.g. physical platforms) that originate data (e.g. from sensors or intelligence sources) that is processed and exploited at different points in the network.
Case 1: information is exploited at every node (supporting a distributed decision making algorithm where every node makes decisions using the same data).
Case 2: information is exploited by a single node in the network (supporting a centralised decision scheme).
Case 1: Information Exploitation at Every Node
On-Network Computation: Define Ro the rate at which a node produces data packets of fixed size So. Then the total amount of data produced per unit time scales as N2R0, where N is the number of agents in the system, and the bandwidth consumption is N2RoSo—see FIG. 1(a).
In-Network Computation: Suppose a node can produce processed information, at a controlled rate, in packets of size S1, that summarises the raw data received to date. The node then sends this information to other nodes. On receiving a message containing new information, a node can integrate this information into the next message sent to other nodes—see FIG. 1(b). If the network is tree-like (has N−1 links), and each node generates messages at rate RI, then the total bandwidth used is NRISI—see FIG. 1(b).
Therefore the In-Network solution has lower resource usage whenRISI<<NRoSO,assuming the timeliness and accuracy of the two solutions are identical. Furthermore, the In-Network solution can control the rate at which it sends without losing information (if it sends accurate summaries of data) giving it the ability to control its emissions to match EMCON requirements.Case 2: Information Exploitation at a Single Node
On-Network Computation: If a single node needs to receive information from all others, the total network resource used per message will be proportional to the path length of each message, say Nα, where α<1 which is bounded by N. Then, the total network resource utilised is Nα+1RoSo.
In-Network Computation: For this case, the same scaling can be adopted again as before i.e. resource consumption scales as NRISI. In this case, information is produced at every node, but only consumed at one node.
Therefore, assuming α is zero (favourable to the On-Network case) preference of one strategy over another is solely dependent on the ratioRISI/RoSo,so that even in a centralised application, there may be benefits to be derived from a smart In-Network computational approach. The inventors' approach to an In-Network solution is demonstrated hereinafter.Technical Challenges
It is now instructive to turn one's focus to the implementation of distributed decision making algorithms using Bayesian Decision Theory. This allows current and future state uncertainty to be treated consistently within the Bayesian paradigm, and allows decisions to be weighted according to cost or reward, as defined by some utility function (see Reference [2]). Formally, Bayesian decision theory generalises stochastic programming (see Reference [3]) and Markov Decision Processes (see Reference [4]), and other techniques used for decision making under uncertainty.
Within this framework, the goal of the information gathering system is to make a series of local decisions (e.g. sense, communicate, manoeuvre) to maximise the total utility of the data gathered:
                              argmax          a                ⁢                              ∑            X                    ⁢                                    U              ⁡                              (                                  X                  ,                  a                                )                                      ⁢                          P              ⁡                              (                                                      X                    ❘                    z                                    ,                  a                                )                                                                        (        1        )            where X={X1, . . . , XN} is the set of variables that describe the world, U(X,a) is a utility or relevance function and a and z denote a set of actions and observations respectively. In this specification a bold font is used to indicate a set, and a normal font to indicate a member of the set. Lower case will be used to indicate a particular element drawn from a set. Hence z={z1=Zj, z2=Zk, . . . , zN=ZQ} represents a set of observations drawn from Z and a={a1=Aj, a2=Ak, . . . , aN=AQ} a set of actions drawn from A. The probability distribution P(X|z,a) therefore represents the state of knowledge of the world, given a set of actions a and observations z. In the sections hereinafter the challenges of implementing Bayesian decision theory in the inventors' proposed application are explored.Distribution of Information
Equation (1) above describes the optimisation of a utility function in which information about the current state P(X|z,a) and the utility function are available concurrently.
According to the inventors' application, each node has to maintain its own model of the world, which differs between nodes only in the information used to update the initial prior model. However, if the models differ appreciably between nodes, then the potential exists that the decisions made by any two models will be inconsistent.